#pragma once

#include <array>
#include <cassert>
#include <memory>
#include "noncopyable.hpp"
#include "random.hpp"


template <typename T, typename Compare>
class skip_list;

template <typename T, typename Compare>
class skip_list_iterator;

template <typename T, typename Compare>
class skip_list_node : public noncopyable
{
    struct skip_list_level_t
    {
        size_t span_;           //该层当前节点到该层下一个节点间的节点个数
        skip_list_node* next_;  //该层的下一个节点
        skip_list_node* prev_;  //该层的前一个节点.主要简化删除时间复杂度
    };

    friend class skip_list<T, Compare>;
    friend class skip_list_iterator<T, Compare>;

public:
    using size_type       = size_t;
    using difference_type = ptrdiff_t;
    using value_type      = T;
    using pointer         = T*;
    using reference       = T&;
    using const_pointer   = const T*;
    using const_reference = const T&;

    constexpr skip_list_node(size_type height, const value_type& value) noexcept
            : value_(value),
              height_(height),
              levels_(new skip_list_level_t[height])
    {
        assert(height_ > 0);
    }

    constexpr explicit skip_list_node(size_type height, value_type&& value = value_type()) noexcept
            : value_(std::move(value)),
              height_(height),
              levels_(new skip_list_level_t[height])
    {
        assert(height_ > 0);
    }

    ~skip_list_node() noexcept { delete[] levels_; }

private:
    value_type value_;           //节点值
    size_type height_;           //层高
    skip_list_level_t* levels_;  //层数据
};

template <typename T, typename Compare>
class skip_list_iterator
{
public:
    using node_type         = skip_list_node<T, Compare>;
    using size_type         = typename node_type::size_type;
    using difference_type   = typename node_type::difference_type;
    using value_type        = typename node_type::value_type;
    using pointer           = typename node_type::pointer;
    using reference         = typename node_type::reference;
    using const_pointer     = typename node_type::const_pointer;
    using const_reference   = typename node_type::const_reference;
    using iterator_category = std::bidirectional_iterator_tag;

    constexpr skip_list_iterator() noexcept : node_(nullptr) {}
    constexpr explicit skip_list_iterator(const node_type* node) noexcept : node_(node) {}
    constexpr const_pointer operator->() const noexcept { return &(node_->value_); }
    constexpr const_reference operator*() const noexcept { return (node_->value_); }

    constexpr skip_list_iterator& operator++() noexcept
    {
        node_ = node_->levels_[0].next_;
        return (*this);
    }

    constexpr skip_list_iterator operator++(int) noexcept
    {
        auto result = *this;
        node_       = node_->levels_[0].next_;
        return result;
    }

    constexpr skip_list_iterator& operator--() noexcept
    {
        node_ = node_->levels_[0].prev_;
        return (*this);
    }

    constexpr skip_list_iterator operator--(int) noexcept
    {
        auto result = *this;
        node_       = node_->levels_[0].prev_;
        return result;
    }

    constexpr bool operator==(const skip_list_iterator& that) const noexcept { return (node_ == that.node_); }

    constexpr const node_type* node() const noexcept { return node_; }

private:
    const node_type* node_;
};

template <typename T, typename Compare = std::less<T>>
class skip_list : public noncopyable
{
    static constexpr size_t kMaxSkipListLevel = 32;
    static constexpr double kAddLevelRatio    = 0.3;  //多一层的概率

public:
    using node_type        = skip_list_node<T, Compare>;
    using size_type        = typename node_type::size_type;
    using value_type       = typename node_type::value_type;
    using pointer          = typename node_type::pointer;
    using reference        = typename node_type::reference;
    using const_pointer    = typename node_type::const_pointer;
    using const_reference  = typename node_type::const_reference;
    using iterator         = skip_list_iterator<T, Compare>;
    using reverse_iterator = std::reverse_iterator<iterator>;

public:
    constexpr skip_list() noexcept : header_(nullptr), length_(0), height_(0) { init(); }
    ~skip_list() noexcept { free(); }

    [[nodiscard]] constexpr size_type size() const noexcept { return length_; }
    [[nodiscard]] constexpr bool empty() const noexcept { return length_ == 0; }

    constexpr void clear() noexcept
    {
        free();

        init();
    }

    constexpr reference front() noexcept
    {
        assert(!empty());
        return header_->levels_[0].next_->value_;
    }

    constexpr const_reference front() const noexcept
    {
        assert(!empty());
        return header_->levels_[0].next_->value_;
    }

    constexpr reference back() noexcept
    {
        assert(!empty());
        return header_->levels_[0].prev_->value_;
    }

    constexpr const_reference back() const noexcept
    {
        assert(!empty());
        return header_->levels_[0].prev_->value_;
    }

    constexpr const_reference at(size_type pos) const noexcept
    {
        assert(pos < size());

        return find_by_index(pos).node()->value_;
    }

    constexpr const_reference operator[](size_type pos) const noexcept { return at(pos); }
    constexpr iterator begin() const noexcept { return iterator(header_->levels_[0].next_); }
    constexpr iterator end() const noexcept { return iterator(header_); }
    constexpr reverse_iterator rbegin() const noexcept { return reverse_iterator(end()); }
    constexpr reverse_iterator rend() const noexcept { return reverse_iterator(begin()); }

    constexpr size_type index(iterator iter) const noexcept
    {
        size_type step   = 0;
        const auto* node = iter.node();
        while (node != header_)
        {
            auto level_index = node->height_ - 1;
            step += node->levels_[level_index].span_;
            node = node->levels_[level_index].next_;
        }
        return size() - step;
    }

    template <typename Type>
    constexpr iterator insert(Type&& value) noexcept
    {
        std::array<uint32_t, kMaxSkipListLevel> prev_index {};
        std::array<node_type*, kMaxSkipListLevel> prev_nodes {};

        auto new_level = random_level();
        auto new_node  = std::make_unique<node_type>(new_level, std::forward<Type>(value));

        auto* temp = header_;
        for (auto index = static_cast<int32_t>(height_ - 1); index >= 0; --index)
        {
            prev_index[index] = (index == static_cast<int32_t>(height_ - 1) ? 0 : prev_index[index + 1]);
            while ((header_ != temp->levels_[index].next_)
                   && (cmp_(new_node->value_, temp->levels_[index].next_->value_) == false))
            {
                prev_index[index] += temp->levels_[index].span_;
                temp = temp->levels_[index].next_;
            }

            prev_nodes[index] = temp;
        }

        if (new_level > height_)
        {
            for (size_type index = height_; index < new_level; ++index)
            {
                prev_index[index]                       = 0;
                prev_nodes[index]                       = header_;
                prev_nodes[index]->levels_[index].span_ = length_ + 1;
            }

            height_ = new_level;
        }

        for (size_type index = 0; index < new_level; ++index)
        {
            new_node->levels_[index].next_                       = prev_nodes[index]->levels_[index].next_;
            new_node->levels_[index].prev_                       = prev_nodes[index];
            prev_nodes[index]->levels_[index].next_              = new_node.get();
            new_node->levels_[index].next_->levels_[index].prev_ = new_node.get();

            // update span covered by update[index] as new skip_list_node is inserted here
            new_node->levels_[index].span_ = prev_nodes[index]->levels_[index].span_ - (prev_index[0] - prev_index[index]);
            prev_nodes[index]->levels_[index].span_ = prev_index[0] - prev_index[index] + 1;
        }

        for (size_type index = new_level; index < height_; ++index)
        {
            ++prev_nodes[index]->levels_[index].span_;
        }

        ++length_;

        return iterator(new_node.release());
    }

    template <typename... Args>
    constexpr iterator emplace(Args... args) noexcept
    {
        return insert(value_type { std::forward<Args>(args)... });
    }

    constexpr iterator erase(iterator posIter) noexcept
    {
        if (posIter == end())
        {
            return (end());
        }

        const node_type* posNode = posIter.node();
        const auto posMaxLevel   = posNode->height_;
        iterator nextIter(posNode->levels_[0].next_);
        for (size_type index = 0; index < posMaxLevel; ++index)
        {
            posNode->levels_[index].prev_->levels_[index].next_ = posNode->levels_[index].next_;
            posNode->levels_[index].next_->levels_[index].prev_ = posNode->levels_[index].prev_;

            //减去要删除节点
            auto selfSpan                                       = posNode->levels_[index].span_;
            auto prevSpan                                       = posNode->levels_[index].prev_->levels_[index].span_ - 1;
            posNode->levels_[index].prev_->levels_[index].span_ = selfSpan + prevSpan;
        }

        if ((posMaxLevel == height_) && (posNode->levels_[posMaxLevel - 1].prev_ == header_)
            && (posNode->levels_[posMaxLevel - 1].next_ == header_))
        {
            --height_;
        }
        else
        {
            auto tempMaxLevel = posMaxLevel;
            const auto* temp  = posNode->levels_[posMaxLevel - 1].prev_;
            while (tempMaxLevel < height_)
            {
                if (temp->height_ <= tempMaxLevel)
                {
                    temp = temp->levels_[temp->height_ - 1].prev_;
                }
                else
                {
                    --temp->levels_[tempMaxLevel].span_;
                    ++tempMaxLevel;
                }
            }
        }

        --length_;
        delete posNode;

        return nextIter;
    }

    constexpr iterator erase(iterator begin, iterator end) noexcept
    {
        auto iter = begin;
        while (iter != end)
        {
            iter = erase(iter);
        }
        return iter;
    }

    constexpr size_type erase(const value_type& value) noexcept
    {
        auto old_size    = size();
        const auto range = equal_range(value);
        erase(range.first, range.second);
        return old_size - size();
    }

    /**
     * 返回第一个大于或等于value的元素位置
     * @param value
     * @return 查找元素位置的迭代器
     */
    constexpr iterator lower_bound(const value_type& value) const noexcept
    {
        size_type rank = 0;
        auto* temp     = header_;
        for (auto index = static_cast<int32_t>(height_ - 1); index >= 0; --index)
        {
            while (header_ != temp->levels_[index].next_ && (cmp_(temp->levels_[index].next_->value_, value) == true))
            {
                rank += temp->levels_[index].span_;
                temp = temp->levels_[index].next_;
            }
        }

        return iterator(temp->levels_[0].next_);
    }

    /**
     * 返回第一个大于value的元素位置
     * @param value
     * @return 查找元素位置的迭代器
     */
    constexpr iterator upper_bound(const value_type& value) const noexcept
    {
        size_type rank = 0;
        auto* temp     = header_;
        for (auto index = static_cast<int32_t>(height_ - 1); index >= 0; --index)
        {
            while ((header_ != temp->levels_[index].next_) && (cmp_(value, temp->levels_[index].next_->value_) == false))
            {
                rank += temp->levels_[index].span_;
                temp = temp->levels_[index].next_;
            }
        }

        return iterator(temp->levels_[0].next_);
    }

    constexpr std::pair<iterator, iterator> equal_range(const value_type& value) const noexcept
    {
        return std::make_pair(lower_bound(value), upper_bound(value));
    }

    constexpr iterator find_first_of(const value_type& value) const noexcept
    {
        auto iter = lower_bound(value);
        return (iter != end() && cmp_(*iter, value) == false && cmp_(value, *iter) == false) ? iter : end();
    }

    constexpr iterator find_by_index(size_type pos) const noexcept
    {
        if (pos >= size())
        {
            return end();
        }

        auto* temp = header_;
        auto left  = pos;
        for (auto index = static_cast<int64_t>(height_ - 1); left > 0 && index >= 0; --index)
        {
            while (left >= temp->levels_[index].span_)
            {
                left -= temp->levels_[index].span_;
                temp = temp->levels_[index].next_;
            }
        }

        return iterator(temp->levels_[0].next_);
    }

    constexpr size_type count(const value_type& value) const noexcept
    {
        return index(upper_bound(value)) - index(lower_bound(value));
    }

    constexpr bool contains(const value_type& value) const noexcept { return find_first_of(value) != end(); }

    void dump() noexcept
    {
        std::string strSep = "|";
        printf("LENGTH:%lu|MAX_LEVEL:%lu\n", length_, height_);
        printf("idx%s", strSep.c_str());
        node_type* pTmp      = header_->levels_[0].next_;
        unsigned int uiIndex = 0;
        while (pTmp != header_)
        {
            printf("%3u%s", uiIndex, strSep.c_str());
            uiIndex++;
            pTmp = pTmp->levels_[0].next_;
        }
        printf("\n");

        printf("num%s", strSep.c_str());
        pTmp = header_->levels_[0].next_;
        while (pTmp != header_)
        {
            if constexpr (sizeof pTmp->value_ == 4)
            {
                printf("%3d%s", pTmp->value_, strSep.c_str());
            }
            else
            {
                printf("%3lu%s", pTmp->value_, strSep.c_str());
            }

            pTmp = pTmp->levels_[0].next_;
        }

        printf("\n");

        for (unsigned int i = 0; i < height_; i++)
        {
            printf("%3zu%s", header_->levels_[i].span_, strSep.c_str());
            pTmp                    = header_->levels_[i].next_;
            node_type* pCurrentNode = header_->levels_[0].next_;
            while (pTmp != header_)
            {
                while (pCurrentNode != pTmp)
                {
                    printf("   %s", strSep.c_str());
                    pCurrentNode = pCurrentNode->levels_[0].next_;
                }

                printf("%3zu%s", pTmp->levels_[i].span_, strSep.c_str());
                pTmp         = pTmp->levels_[i].next_;
                pCurrentNode = pCurrentNode->levels_[0].next_;
            }

            printf("\n");
        }
    }

private:
    static size_type random_level() noexcept
    {
        size_type level = 1;
        while (static_cast<double>(randint() & 0xffffU) < (kAddLevelRatio * 0xffff))
        {
            if ((++level) >= kMaxSkipListLevel)
            {
                break;
            }
        }

        return level;
    }

    constexpr void free() noexcept
    {
        auto* node = header_->levels_[0].next_;

        while (node != header_)
        {
            auto next = node->levels_[0].next_;
            delete node;
            node = next;
        }

        delete header_;
    }

    constexpr void init() noexcept
    {
        header_ = new node_type(kMaxSkipListLevel);
        for (size_type i = 0; i < kMaxSkipListLevel; ++i)
        {
            header_->levels_[i].span_ = 1;
            header_->levels_[i].next_ = header_;
            header_->levels_[i].prev_ = header_;
        }

        length_ = 0;
        height_ = 1;
    }

private:
    Compare cmp_;        //比较器
    node_type* header_;  //头结点
    size_type length_;   //长度
    size_type height_;   //层高
};
